package com.cuz.daileetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Day42 {
    /**
     * 假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。
     * <p>
     * 这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息：
     * <p>
     * 必须接送的乘客数量；
     * 乘客的上车地点；
     * 以及乘客的下车地点。
     * 这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。
     * <p>
     * 请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务
     * （当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。
     * <p>
     *
     * <p>
     * 示例 1：
     * <p>
     * 输入：trips = [[2,1,5],[3,3,7]], capacity = 4
     * 输出：false
     * 示例 2：
     * <p>
     * 输入：trips = [[2,1,5],[3,3,7]], capacity = 5
     * 输出：true
     * 示例 3：
     * <p>
     * 输入：trips = [[2,1,5],[3,5,7]], capacity = 3
     * 输出：true
     * 示例 4：
     * <p>
     * 输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
     * 输出：true
     *
     * <p>
     * 提示：
     * <p>
     * 你可以假设乘客会自觉遵守 “先下后上” 的良好素质
     * trips.length <= 1000
     * trips[i].length == 3
     * 1 <= trips[i][0] <= 100
     * 0 <= trips[i][1] < trips[i][2] <= 1000
     * 1 <= capacity <= 100000
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/car-pooling
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @author 80309525
     * @version 1.0
     * @date 2022/2/9
     */
    public static class L1094 {

        /***
         * trips = [[3,1,10],[3,2,9],[8,3,9]], capacity = 11
         * [[乘客数量，地点，下车顺序]]
         * @return
         */
        public static boolean l1094(int[][] trips, int capacity) {
            if (trips == null || trips.length == 0 || capacity < 0) {
                return true;
            }
            //根据上车顺序排序
            Arrays.sort(trips, Comparator.comparing(a -> a[1]));
            //根据下车顺序排序小根堆，堆顶是最先下车的
            PriorityQueue<int[]> heapPersonTaskOff = new PriorityQueue<>(Comparator.comparing(a -> a[2]));
            //顺序是 上车顺序
            for (int[] temp : trips) {
                //乘客数量 上车
                int curPersonNum = temp[0];
                //当前站
                int port = temp[1];
                //上车的人减少容量
                capacity -= curPersonNum;
                if (capacity < 0) {
                    //下车
                    while (!heapPersonTaskOff.isEmpty() && heapPersonTaskOff.peek()[2] <= port) {
                        capacity += heapPersonTaskOff.poll()[0];
                    }
                    if (capacity < 0) {
                        return false;
                    }
                }
                //加入到堆
                heapPersonTaskOff.offer(temp);
            }
            return true;
        }
    }

    /**********
     * 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
     *
     *
     *
     * 示例 1 :
     *
     * 输入:nums = [1,1,1], k = 2
     * 输出: 2
     * 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
     * 示例 2 :
     *
     * 输入:nums = [1,2,3], k = 3
     * 输出: 2
     *
     *
     * 提示:
     *
     * 1 <= nums.length <= 2 * 104
     * -1000 <= nums[i] <= 1000
     * -107 <= k <= 107
     *
     *
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/QTMn0o
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static class O10 {
        public static int subArraySumCountPrefixSum(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int sum = 0;
            int count = 0;
            HashMap<Integer, Integer> prefixSumCountMap = new HashMap<>();
            prefixSumCountMap.put(0, 1);
            for (int temp : nums) {
                sum += temp;
                count += prefixSumCountMap.getOrDefault(sum - k, 0);
                prefixSumCountMap.put(sum, prefixSumCountMap.getOrDefault(sum, 0) + 1);
            }
            return count;
        }

        public static int subArraySumCountDp(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int count = 0;
            int len = nums.length;
            int[][] dp = new int[len][len];
            for (int row = 0; row < len; row++) {
                for (int col = 0; col <= row; col++) {
                    if (col == row) {
                        dp[row][col] = nums[row];
                    } else {
                        dp[row][col] = dp[row - 1][col] + nums[row];
                    }
                    if (dp[row][col] == k) {
                        count++;
                    }
                }
            }
            return count;
        }

        public static void main(String[] args) {
            int[] ints = {217,-315,-999,-537,116,46,971
                    ,31,-978,-796,-613,80,-668,952,505,
                    306,-405,884,435,-795,89,539,170,
                    -963,360,-27,699,951,440,-163,-996,
                    820,-548,400,-898,803,-771,-263,9,
                    320,-163,-156,142,689,-222,-156,-860};
            int i = subArraySumCountDp(ints, 803);
            int j = subArraySumCountPrefixSum(ints, 803);
            System.out.println(i);
            System.out.println(j);
        }
    }

}
